package com.example.graph;

/**
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，
 * 并将这些区域里所有的 'O' 用 'X' 填充
 *  示例 1：
 *
 * 输入：
 * board =
 * {{"X","X","X","X"},
 *  {"X","O","O","X"},
 *  {"X","X","O","X"},
 *  {"X","O","X","X"}}
 * 输出：
 * {{"X","X","X","X"},
 *  {"X","X","X","X"},
 *  {"X","X","X","X"},
 *  {"X","O","X","X"}}
 *
 *  示例二:
 *  输入:
 *  board = {
 * {'X', 'X', 'X', 'X', 'X'},
 * {'X', 'X', 'X', 'O', 'X'},
 * {'X', 'X', 'X', 'X', 'X'},
 * {'X', 'X', 'X', 'X', 'X'},
 * {'X', 'O', 'O', 'X', 'X'},
 * {'X', 'O', 'X', 'X', 'X'},
 * {'O', 'X', 'O', 'X', 'X'},
 * {'O', 'O', 'O', 'X', 'X'},
 * {'X', 'O', 'X', 'X', 'X'}}
 * 输出:{
 * {'X', 'X', 'X', 'X', 'X'},
 * {'X', 'X', 'X', 'X', 'X'},
 * {'X', 'X', 'X', 'X', 'X'},
 * {'X', 'X', 'X', 'X', 'X'},
 * {'X', 'X', 'X', 'X', 'X'},
 * {'X', 'X', 'X', 'X', 'X'},
 * {'O', 'X', 'O', 'X', 'X'},
 * {'O', 'O', 'O', 'X', 'X'},
 * {'X', 'O', 'X', 'X', 'X'}};
 *
 * 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的'O'都不会被填充为'X'。
 * 任何不在边界上，或不与边界上的'O'相连的'O'最终都会被填充为'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 *
 */
public class Leetcode130_Solve {

    public static void main(String[] args) {

//        char[][] board = {
//                {'X','X','X','X'},
//                {'X','O','O','X'},
//                {'X','X','O','X'},
//                {'X','O','X','X'}};

        char[][] board = {
                {'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'O', 'X'},
                {'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X', 'X'},
                {'X', 'O', 'X', 'X', 'X'},
                {'O', 'X', 'O', 'X', 'X'},
                {'O', 'O', 'O', 'X', 'X'},
                {'X', 'O', 'X', 'X', 'X'}};


        new Solution().solve(board);

        for (char[] b : board) {
            for (char c : b) {
                System.out.print(c + ",");
            }
            System.out.println();
        }

    }

    static class Solution {
        /**
         * 首先搜索边缘四周的'O'，发现后DFS将相连的'O'改成'#',因为与边界相连的'O'不需要变成'X'
         *
         * 然后遍历二维数组将'O'变为'X'（因为不和边界相连），把#变为O（因为和边界相连）。
         * @param board
         */
        public void solve(char[][] board) {
            int row = board.length;
            int column = board[0].length;
            if (board == null || row <= 1 || column <= 1) {
                return;
            }

            // 1.搜索边缘,把与边缘相连的'O'变为'#', 代表和边界相连。
            for (int i = 0; i < row; i++) {
                dfs(board, i, 0, row ,column); // 第一列
                dfs(board, i, column - 1, row ,column); // 最后一列
            }
            for (int i = 1; i < column - 1; i++) {
                dfs(board, 0, i, row ,column); // 第一行(除掉首尾)
                dfs(board, row - 1, i, row ,column);// 最后一行(除掉首尾)
            }


            // 2.遍历数组，把'O'变为'X'（因为不和边界相连），把#变为O（因为和边界相连）。
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < column; j++) {
                    //没有被搜索到过，不和边界连接
                    if (board[i][j] == 'O') {
                        board[i][j] = 'X';
                    }
                    //被改变过，和边界连接
                    if (board[i][j] == '#') {
                        board[i][j] = 'O';
                    }
                }
            }

        }

        private void dfs(char[][] board, int x, int y, int row, int column) {
            if (x < 0 || y < 0 || x >= row || y >= column || board[x][y] != 'O')
                return;
            board[x][y] = '#';
            dfs(board, x - 1, y, row, column);
            dfs(board, x + 1, y, row, column);
            dfs(board, x, y - 1, row, column);
            dfs(board, x, y + 1, row, column);
        }
    }
}
